class Solution {
    /**
    前序遍历是：root left right，
    后续遍历是：left right root，

    如果是向右递归遍历，那么list是：root right left
    
     */
    public List<Integer> postorderTraversal(TreeNode root) {

        LinkedList<Integer> res = new LinkedList<>();
        Deque<TreeNode> stack =  new LinkedList<>();
        while (root!=null || stack.size()>0){
            // 向右边递归搜索,那么list是[root,right,left]
            // 所以list 反转后就是后续遍历了
            // https://zhuanlan.zhihu.com/p/73438175
            while (root!=null){
                res.addFirst(root.val);
                stack.push(root);
                root = root.right;
            }
            if(stack.size()>0){
                TreeNode tmp = stack.pop();
                root = tmp.left;
            }
        }

        return res;
    }
}